import java.util.Stack;

/**
 * @ Author     ：侯耀祖
 * @ Description：${description}
 */// 按两次 Shift 打开“随处搜索”对话框并输入 `show whitespaces`，
// 然后按 Enter 键。现在，您可以在代码中看到空格字符。
public class Main {
    public static void main(String[] args) {
        String str = "(2*(3-4))*5";
        postfix(str);
    }
    /**
     * 将中缀表达式转换为后缀表达式
     * @param s 中缀表达式
     * @return String字符串 后缀表达式
     */
    private static String postfix(String s){
        // 后缀表达式
        StringBuilder sb = new StringBuilder();
        Stack<Character> ops = new Stack<>();
        int i = 0;
        while(i < s.length()){
            char c = s.charAt(i++);
            if (c == '(' || c == '+' || c == '-' || c == '*'){
                // 加一个空格是为了将操作数之间隔开
                sb.append(" ");
                pushOP(sb,c,ops);
                continue;
            }
            if (c == ')'){
                // 弹出操作符直到(
                while(ops.peek() != '('){
                    sb.append(ops.pop());
                }
                ops.pop();
                continue;
            }
            sb.append(c);
        }
        // 弹出栈中元素
        while(!ops.isEmpty()){
            sb.append(ops.pop());
        }
        return sb.toString();
    }
    private static void pushOP(StringBuilder sb,char op,Stack<Character> ops){
        // 栈空，或者栈顶元素为(,操作符直接放入栈中
        if (ops.isEmpty() || ops.peek() == '(' || op == '('){
            ops.add(op);
            return;
        }
        char c = ops.peek();
        // 栈顶操作符的优先级低于当前操作符，直接压入栈中
        if (c != '*' && op == '*'){
            ops.add(op);
            return;
        }
        // 否则，弹出栈顶元素，继续比较
        c = ops.pop();
        sb.append(c);
        pushOP(sb,op,ops);
    }
}